package cn.com.code.hwjs;

import java.util.Scanner;

/**
 * 计算字符串的编辑距离
 * https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&tqId=21275&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E5%2590%258D%25E4%25BC%2581%25E7%25AC%2594%25E8%25AF%2595%25E7%259C%259F%25E9%25A2%2598%26topicId%3D37&difficulty=3&judgeStatus=undefined&tags=&title=
 *
 * @author zhengpei
 * @date 2022/5/2
 */
public class Hwjs52 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
      //输入字符串A
      String s1 = sc.next();
      //输入字符串B
      String s2 = sc.next();
      //计算字符串A和字符串B的距离
      System.out.println(distance(s1, s2));
    }
  }

  private static int distance(String s1, String s2) {
    int m = s1.length();
    int n = s2.length();

    int[][] dp = new int[m + 1][n + 1];
    // 初始化状态
    for (int i = 1; i <= m; i++) {
      dp[i][0] = i;
    }
    for (int j = 1; j <= n; j++) {
      dp[0][j] = j;
    }

    // 转移状态
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        //如果相等，直接等于前一个位置的情况
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          /**
           如果不相等，要么B字符串插入A中i位置对应字符即dp[i][j]=dp[i-1][j]+1
           要么A字符串插入B中j位置对应字符即dp[i][j]=dp[i][j-1]+1，要么s1字符串
           i位置字符被s2字符串j位置字符替换，即dp[i][j]=dp[i-1][j-1]+1
           */
          dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
        }
      }
    }
    return dp[m][n];
  }

}
